package com.algorithm.ch1.lzr.array;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

/**
 * 加1 核心是对于边界值+1之后, 进位的处理
 *
 * @author lzr
 * @date 2018/8/7
 */
public class PlusOne {

    public static void main(String[] args) {
        //假如输入是99999, 那么99999 + 1 = 100000
        int[] array1 = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        int[] array2 = {9, 9, 9, 9, 9, 9};
        int[] array3 = {9, 9, 9, 9, 8, 9};
        int[] ints1 = plusOne1(array1);
        int[] ints2 = plusOne2(array2);
        int[] ints3 = plusOne3(array3);
        System.out.println("使用方式1: ");
        for (int i = 0; i < ints1.length; i++) {
            System.out.println(ints1[i]);
        }
        System.out.println("使用方式2: ");
        for (int i = 0; i < ints2.length; i++) {
            System.out.println(ints2[i]);
        }
        System.out.println("使用方式3: ");
        for (int i = 0; i < ints3.length; i++) {
            System.out.println(ints3[i]);
        }
    }

    /**
     * 数组a [9,9,9,8]这样的数组 直接加1 [9,9,9,9]
     * 数组b [9,9,8,9]这样的数组 从最后一位运行,如果a[i]=9, 让a[i]=0, 直到a[i]≠9, 直接加1 [9,9,9,9]
     * 数组c [9,9,9,9]这样的数组 利用new int[a.length+1] = [0,0,0,0,0], 再将a[0] = 1 实现 [1,0,0,0,0]
     *
     * @param array
     * @return
     */
    public static int[] plusOne1(int[] array) {
        int length = array.length;
        for (int i = length - 1; i > -1; i--) {
            if (array[i] == 9) {
                array[i] = 0;
            } else {
                array[i] += 1;
                return array;
            }
        }
        //如果整个数组都是9
        int[] newArray = new int[length + 1];
        newArray[0] = 1;
        return newArray;
    }

    /**
     * 使用集合来处理
     *
     * @param array
     * @return
     */
    public static int[] plusOne2(int[] array) {
        //对于整数0的处理
        if (array.length == 1 && array[0] == 0) {
            return new int[]{1};
        }
        //倒序进行计算
        List<Integer> list = new ArrayList<>();
        Boolean flag = true;
        for (int i = array.length - 1; i >= 0; i--) {
            if (flag) {
                if (array[i] == 9) {
                    list.add(0);
                    flag = true;
                } else {
                    list.add(array[i] + 1);
                    flag = false;
                }
            } else {
                list.add(array[i]);
            }
        }
        if (list.get(list.size() - 1) == 0) {
            list.add(1);
        }
        int[] temp = new int[list.size()];
        //倒序遍历集合
        for (int i = list.size() - 1; i >= 0; i--) {
            temp[list.size() - 1 - i] = list.get(i);
        }
        return temp;
    }


    /**
     * 使用字符串来处理, 在数组长度过长的场景下不适用
     * 对于[1,3,4]转成字符串134 或 [9,9,9]转成字符串999, 再转成BigInteger类型进行 +1 运算, 再转成字符串, 最后使用字符串截取的方式转成数组
     * 如果字符串可能太长, 使用Integer或者Long转化String, 会抛出NumberFormatException异常, 所以这里使用BigInteger来对字符串做转换
     *
     * @param array
     * @return
     */
    public static int[] plusOne3(int[] array) {
        if (array.length == 1 && array[0] == 0) {
            return new int[]{1};
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            sb.append(array[i]);
        }
        BigInteger b = new BigInteger(sb.toString()).add(BigInteger.ONE);
        String value = String.valueOf(b);
        int[] temp = new int[value.length()];
        //重新转成数组
        for (int i = 0; i < value.length(); i++) {
            temp[i] = Integer.valueOf(value.substring(i, i + 1));
        }
        return temp;
    }

}
